{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Repeating Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #string-matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxRepeating"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大重复子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>sequence</code> ，如果字符串 <code>word</code> 连续重复 <code>k</code> 次形成的字符串是 <code>sequence</code> 的一个子字符串，那么单词 <code>word</code> 的 <strong>重复值为 <code>k</code></strong><strong> </strong>。单词 <code>word</code> 的 <strong>最</strong><strong>大重复值</strong> 是单词 <code>word</code> 在 <code>sequence</code> 中最大的重复值。如果 <code>word</code> 不是 <code>sequence</code> 的子串，那么重复值 <code>k</code> 为 <code>0</code> 。</p>\n",
    "\n",
    "<p>给你一个字符串 <code>sequence</code> 和 <code>word</code> ，请你返回 <strong>最大重复值 <code>k</code> </strong>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>sequence = \"ababc\", word = \"ab\"\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\"abab\" 是 \"<strong>abab</strong>c\" 的子字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>sequence = \"ababc\", word = \"ba\"\n",
    "<b>输出：</b>1\n",
    "<strong>解释：</strong>\"ba\" 是 \"a<strong>ba</strong>bc\" 的子字符串，但 \"baba\" 不是 \"ababc\" 的子字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>sequence = \"ababc\", word = \"ac\"\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>\"ac\" 不是 \"ababc\" 的子字符串。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= sequence.length <= 100</code></li>\n",
    "\t<li><code>1 <= word.length <= 100</code></li>\n",
    "\t<li><code>sequence</code> 和 <code>word</code> 都只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-repeating-substring](https://leetcode.cn/problems/maximum-repeating-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-repeating-substring](https://leetcode.cn/problems/maximum-repeating-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ababc\"\\n\"ab\"', '\"ababc\"\\n\"ba\"', '\"ababc\"\\n\"ac\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        def subString(s,w):\n",
    "            ls = len(s)\n",
    "            lw = len(w)\n",
    "            i = 0\n",
    "            while i + lw <= ls:\n",
    "                if s[i:i+lw] == w:\n",
    "                    return True\n",
    "                i += 1    \n",
    "            return False\n",
    "\n",
    "        n = len(sequence)\n",
    "        k = 0\n",
    "        w = word\n",
    "        while len(w)<=n:\n",
    "            if subString(sequence,w):\n",
    "                k +=1\n",
    "                w = word*(k+1)\n",
    "            else:\n",
    "                break\n",
    "        return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        for k in range(len(sequence) // len(word), -1, -1):\n",
    "            if word * k in sequence:\n",
    "                return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        res = 0\n",
    "        while (res * word) in sequence:\n",
    "            res += 1\n",
    "        res -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        words = [word]\n",
    "        while ''.join(words) in sequence:\n",
    "            words.append(word)\n",
    "        return len(words) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        for i in range(len(sequence)//len(word),0,-1):\n",
    "            if word*i in sequence:\n",
    "                return i\n",
    "        return 0       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        ans = 0\n",
    "        words = [word]\n",
    "        while ''.join(words) in sequence:\n",
    "            words.append(word)\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\r\n",
    "        for i in range(int(len(sequence)/len(word)),0,-1):\r\n",
    "            if word*i in sequence:\r\n",
    "                return i\r\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        ans = 0\n",
    "        a = word\n",
    "        while 1:\n",
    "            if word in sequence:\n",
    "                ans += 1\n",
    "                word += a\n",
    "            else:\n",
    "                return ans \n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        words = [word]\n",
    "        while ''.join(words) in sequence:\n",
    "            words.append(word)\n",
    "        return len(words) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        res = 0\n",
    "        aword = word\n",
    "        while word in sequence:\n",
    "            res += 1\n",
    "            word += aword\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        if word not in sequence:\n",
    "            return 0\n",
    "        m = len(word)\n",
    "        n = len(sequence)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i <n:\n",
    "            if sequence[i:].startswith(word):\n",
    "                k = 0\n",
    "                for j in range(i, n, m):\n",
    "                    if sequence[j:j+m] == word:\n",
    "                        k+=1\n",
    "                    else:\n",
    "                        break\n",
    "                ans = max(ans, k)\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        ans = 0\n",
    "        words = word\n",
    "        while words in sequence:\n",
    "            words += word\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        k = 0\n",
    "        newword = word\n",
    "        while newword in sequence:\n",
    "            k += 1\n",
    "            newword += word\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        for k in range(200):\n",
    "            if word*(k+1) not in sequence:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        for k in range(len(sequence) // len(word), -1, -1):\n",
    "            if word * k in sequence:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        ans = 0\n",
    "        while 1:\n",
    "            if word * (ans + 1) in sequence:\n",
    "                ans += 1\n",
    "            else:\n",
    "                return ans \n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        res = 0\n",
    "        while (res * word) in sequence:\n",
    "            res += 1\n",
    "        res -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        res=0\n",
    "        ref=word\n",
    "        while sequence.find(ref)!=-1:\n",
    "            res+=1\n",
    "            ref+=word\n",
    "        return res\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        n = len(sequence) // len(word)\n",
    "        for i in range(n, 0, -1):\n",
    "            if word * i in sequence:\n",
    "                return i\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        k = 0\n",
    "        num = len(sequence) // len(word)\n",
    "        # print(\"num:\", num)\n",
    "        for i in range(1, num + 1):\n",
    "            if (word * i) in sequence:\n",
    "                if i > k:\n",
    "                    k = i\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        n = len(sequence)\n",
    "        m = len(word)\n",
    "        if m > n:\n",
    "            return 0\n",
    "        dp = [0] * n\n",
    "        for i in range(m - 1, n):\n",
    "            valid = True\n",
    "            for j in range(m):\n",
    "                if sequence[i-m+j+1] != word[j]:\n",
    "                    valid = False\n",
    "                    break\n",
    "            if valid:\n",
    "                dp[i] = dp[i-m] + 1\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(sequence) // len(word)+1):\n",
    "            if word * i in sequence:\n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(1,len(sequence)//len(word)+1):\n",
    "            if word*i in sequence:\n",
    "                res = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        if word not in sequence:return 0\n",
    "        k = 0\n",
    "        while 1:\n",
    "            k += 1\n",
    "            if word*k in sequence:continue\n",
    "            else:return k-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        for k in range(len(sequence)//len(word),-1,-1):\n",
    "            if word*k in sequence:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(1,len(sequence)//len(word)+1):\n",
    "            if word*i in sequence:\n",
    "                res = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        if not sequence:\n",
    "            return 0\n",
    "        \n",
    "        m = len(sequence)\n",
    "        n = len(word)\n",
    "        if m<n:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "        dp = [0]*(m+1)\n",
    "\n",
    "        for i in range(n,m+1):\n",
    "            if sequence[i-n:i]==word:\n",
    "                dp[i]=dp[i-n]+1\n",
    "        print(dp)\n",
    "\n",
    "        return max(dp)\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        nw = len(word)\n",
    "        start = 0\n",
    "        rst = 0\n",
    "        while True:\n",
    "            pos = sequence.find(word, start)\n",
    "            if pos == -1:\n",
    "                return rst\n",
    "            print(f\"pos={pos}\")\n",
    "            k = 1\n",
    "            j = pos + nw\n",
    "            while j <= len(sequence) - nw:\n",
    "                if sequence[j:j + nw] == word:\n",
    "                    k += 1\n",
    "                    j += nw\n",
    "                    continue\n",
    "                break\n",
    "            start += 1\n",
    "            rst = max(rst, k)\n",
    "        return rst\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        res = 0\n",
    "        n = len(word)\n",
    "        i = 0\n",
    "        while i < len(sequence):\n",
    "            cnt = 0\n",
    "            j = i\n",
    "            while j + n <= len(sequence) and sequence[j:n+j] == word:\n",
    "                cnt += 1\n",
    "                j += n\n",
    "            i += 1\n",
    "            res = max(res, cnt)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        for k in range(len(sequence) // len(word), -1, -1):\n",
    "            if word * k in sequence:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        nw = len(word)\n",
    "        start = 0\n",
    "        rst = 0\n",
    "        while True:\n",
    "            pos = sequence.find(word, start)\n",
    "            if pos == -1:\n",
    "                return rst\n",
    "            print(f\"pos={pos}\")\n",
    "            k = 1\n",
    "            j = pos + nw\n",
    "            while j <= len(sequence) - nw:\n",
    "                if sequence[j:j + nw] == word:\n",
    "                    k += 1\n",
    "                    j += nw\n",
    "                    continue\n",
    "                break\n",
    "            start = pos + 1\n",
    "            rst = max(rst, k)\n",
    "        return rst\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        def kmp(s: str, m: int):\n",
    "            nxt = [0] * m\n",
    "            j = 0\n",
    "            n = len(s)\n",
    "            for i in range(1, m):\n",
    "                while j > 0 and s[i%n] != s[j%n]:\n",
    "                    j = nxt[j-1]\n",
    "                if s[i%n] == s[j%n]:\n",
    "                    j += 1\n",
    "                nxt[i] = j\n",
    "\n",
    "            return nxt\n",
    "        \n",
    "        \n",
    "        n, m = len(sequence), len(word)\n",
    "        nxt = kmp(word, n)\n",
    "        j = 0          \n",
    "        res = 0\n",
    "        for i in range(n):     \n",
    "            while j > 0 and sequence[i] != word[j%m]:\n",
    "                j = nxt[j-1]\n",
    "            if sequence[i] == word[j%m]:\n",
    "                j += 1\n",
    "            if j // m > res:\n",
    "                res = j // m\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        s = ''\n",
    "        k = 0\n",
    "        ans = 0\n",
    "        while len(s) <= len(sequence):\n",
    "            s += word\n",
    "            k += 1\n",
    "            if s in sequence:\n",
    "                ans = max(k, ans)\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        a=0\n",
    "        if word in sequence:\n",
    "            b=word\n",
    "            while b in sequence:\n",
    "                b=b+word\n",
    "                a+=1\n",
    "            return a\n",
    "        else:\n",
    "            return 0    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        l, ans, length = 0, 0, 0\n",
    "        while l < len(sequence) - len(word) + 1:\n",
    "            if word == sequence[l : l + len(word)]:\n",
    "                length += 1\n",
    "                ans = max(ans, length)\n",
    "                l += len(word)\n",
    "            else:\n",
    "                # 从上一个匹配成功的子字符串的第二个位置开始重新逐个匹配\n",
    "                l = l - len(word) + 1 if length else l + 1\n",
    "                length = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        max_repeat = 0\n",
    "        k = 1\n",
    "        while word * k in sequence:\n",
    "            max_repeat = k\n",
    "            k += 1\n",
    "        return max_repeat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        for i in range(len(sequence)//len(word),-1,-1):\n",
    "            if word * i in sequence:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        for k in range(len(sequence) // len(word), -1, -1):\n",
    "            if word * k in sequence:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        maxs = len(sequence) // len(word)\n",
    "        for i in range(maxs, -1, -1):\n",
    "            if word*i in sequence:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        ans = 0\n",
    "        w = word\n",
    "        while 1:\n",
    "            if w in sequence:\n",
    "                ans+=1\n",
    "                w+=word\n",
    "            else:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        if word not in sequence:return 0\n",
    "        for i in range(1,100):\n",
    "            s=word*i\n",
    "            if s in sequence:\n",
    "                continue\n",
    "            else:\n",
    "                return i-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        k = 0\n",
    "        while word * k in sequence:\n",
    "            k += 1\n",
    "        return k - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        n,m = len(sequence), len(word)\n",
    "        if(n<m):\n",
    "            return 0\n",
    "        f = [0] * n\n",
    "        for i in range(m-1,n):\n",
    "            valid = True\n",
    "            for j in range(m):\n",
    "                if sequence[i - m + j +1] != word[j]:\n",
    "                    valid = False\n",
    "                    break\n",
    "            if valid:\n",
    "                if i == m-1:\n",
    "                    f[i] = 1\n",
    "                else:\n",
    "                    f[i]=f[i-m] + 1\n",
    "\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        maxs = len(sequence) // len(word) \n",
    "        #这行代码计算的是 sequence 字符串中可以容纳 word 字符串的最大整数次数\n",
    "        for i in range(maxs, -1, -1):\n",
    "            if word*i in sequence:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        # 先求出子串能出现的最高次数。\n",
    "        # 如果子串*最高次数在字符串里，那就是它，不在的话就最高次数 -1 继续尝试\n",
    "        maxcount=sequence.count(word)\n",
    "        while True:\n",
    "            if word*maxcount in sequence:\n",
    "                return maxcount\n",
    "            else:\n",
    "                maxcount-=1\n",
    "        return maxcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        n, m = len(sequence), len(word)\n",
    "        if n < m:\n",
    "            return 0\n",
    "        \n",
    "        f = [0] * n\n",
    "        for i in range(m - 1, n):\n",
    "            valid = True\n",
    "            for j in range(m):\n",
    "                if sequence[i - m + j + 1] != word[j]:\n",
    "                    valid = False\n",
    "                    break\n",
    "            if valid:\n",
    "                f[i] = f[i - m] + 1\n",
    "        \n",
    "        return max(f)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        max_k = 0\n",
    "        w_len = len(word)\n",
    "        for i in range(len(sequence)-w_len+1): # 断wlen，但是最后一段还可以作为开头，所以+1\n",
    "            if sequence[i:i+w_len] == word:\n",
    "                k = 1\n",
    "                while i+k*w_len <= len(sequence) and sequence[i+(k-1)*w_len:i+k*w_len] == word:\n",
    "                    k+=1\n",
    "                max_k = max(max_k,k-1)\n",
    "        return max_k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        n, m = len(sequence), len(word)\n",
    "        if n < m:\n",
    "            return 0\n",
    "\n",
    "        fail = [-1] * m\n",
    "        for i in range(1, m):\n",
    "            j = fail[i - 1]\n",
    "            while j != -1 and word[j + 1] != word[i]:\n",
    "                j = fail[j]\n",
    "            if word[j + 1] == word[i]:\n",
    "                fail[i] = j + 1\n",
    "        \n",
    "        f = [0] * n\n",
    "        j = -1\n",
    "        for i in range(n):\n",
    "            while j != -1 and word[j + 1] != sequence[i]:\n",
    "                j = fail[j]\n",
    "            if word[j + 1] == sequence[i]:\n",
    "                j += 1\n",
    "                if j == m - 1:\n",
    "                    f[i] = (0 if i == m - 1 else f[i - m]) + 1\n",
    "                    j = fail[j]\n",
    "        \n",
    "        return max(f)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        for k in range(len(sequence)//len(word),-1,-1):\n",
    "            if word*k in sequence:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        n, m = len(sequence), len(word)\n",
    "        if n < m:\n",
    "            return 0\n",
    "        \n",
    "        f = [0] * n\n",
    "        for i in range(m - 1, n):\n",
    "            valid = True\n",
    "            for j in range(m):\n",
    "                if sequence[i - m + j + 1] != word[j]:\n",
    "                    valid = False\n",
    "                    break\n",
    "            if valid:\n",
    "                f[i] = (0 if i == m - 1 else f[i - m]) + 1\n",
    "        \n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        res = 0\n",
    "        for i in list(range(len(sequence)//len(word) + 1))[::-1]:\n",
    "            if word*i in sequence:\n",
    "                res = i\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        for k in range(len(sequence) // len(word), -1, -1):\n",
    "            if word * k in sequence:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        if word not in sequence:\n",
    "            return 0\n",
    "        else:\n",
    "            for i in range(int(len(sequence)/len(word)),0,-1):\n",
    "                if word*i in sequence:\n",
    "                    return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "\n",
    "        \n",
    "        a = len(word)\n",
    "        b = len(sequence)\n",
    "\n",
    "        s = b//a\n",
    "\n",
    "        while s:\n",
    "\n",
    "            if(word*s in sequence):\n",
    "\n",
    "                return s\n",
    "            else:\n",
    "                s = s - 1\n",
    "            \n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        res = 0\n",
    "        aword = word\n",
    "        while word in sequence:\n",
    "            res += 1\n",
    "            word += aword\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        n, m = len(sequence), len(word)\n",
    "        if n < m:\n",
    "            return 0\n",
    "\n",
    "        fail = [-1] * m\n",
    "        for i in range(1, m):\n",
    "            j = fail[i - 1]\n",
    "            while j != -1 and word[j + 1] != word[i]:\n",
    "                j = fail[j]\n",
    "            if word[j + 1] == word[i]:\n",
    "                fail[i] = j + 1\n",
    "        \n",
    "        f = [0] * n\n",
    "        j = -1\n",
    "        for i in range(n):\n",
    "            while j != -1 and word[j + 1] != sequence[i]:\n",
    "                j = fail[j]\n",
    "            if word[j + 1] == sequence[i]:\n",
    "                j += 1\n",
    "                if j == m - 1:\n",
    "                    f[i] = (0 if i == m - 1 else f[i - m]) + 1\n",
    "                    j = fail[j]\n",
    "        \n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        k = 0\n",
    "        num = len(sequence) // len(word)\n",
    "        for i in range(num, -1, -1):\n",
    "            if (word * i) in sequence:\n",
    "                return i\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        for k in range(len(sequence) // len(word), -1, -1):\n",
    "            if word * k in sequence:\n",
    "                return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        n=len(sequence)\n",
    "        m=len(word)\n",
    "        dp=[0]*n\n",
    "        ans=0\n",
    "        for i in range(n-m+2):\n",
    "            if sequence[i:i+m]==word:\n",
    "                dp[i+m-1]=(dp[i-1] if i-1 >= 0 else 0)+1\n",
    "                ans=max(ans,dp[i+m-1])\n",
    "        return ans\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        if word not in sequence:\n",
    "            return 0\n",
    "        k = 1\n",
    "        word_ = word\n",
    "        n = len(sequence) // len(word)\n",
    "        while k <= n:\n",
    "            word += word_\n",
    "            if word not in sequence:\n",
    "                return k\n",
    "            k += 1\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        k = 1\n",
    "        tmp = word\n",
    "        while tmp in sequence:\n",
    "            tmp += word\n",
    "            k += 1\n",
    "        return k - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        len1=len(sequence)\n",
    "        len2=len(word)\n",
    "        c=len1//len2\n",
    "        t=0\n",
    "        for i in range(1,c+1):\n",
    "            if word*i in sequence:\n",
    "                t+=1\n",
    "        return  t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating_1(self, sequence: str, word: str) -> int:\n",
    "        i = 0\n",
    "        max_k = 0\n",
    "        L = len(word)\n",
    "        while i < len(sequence):\n",
    "            if sequence[i: i+L] == word:\n",
    "                k = 1\n",
    "                while sequence[i+(L*k): i+(L*(k+1))] == word:\n",
    "                    k += 1\n",
    "                if k > max_k:\n",
    "                    max_k = k\n",
    "            i += 1\n",
    "        return max_k\n",
    "\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        L = len(sequence)\n",
    "        valid = [0 for _ in range(L)]\n",
    "        for i in range(L-1, len(word)-2, -1):\n",
    "            if sequence[i-len(word)+1:i+1] == word:\n",
    "                valid[i] = 1\n",
    "        # dp[i]表示sequence[:i+1]中最大重复值（以sequence[i]结尾）\n",
    "        dp = [0 for _ in range(L)]\n",
    "        for i in range(len(word)-1, L):\n",
    "            if valid[i] == 1:\n",
    "                # not i-len(word)+1, 这个是当前状态的第一位，再前一位才是之前状态的最后一位\n",
    "                if i == len(word) - 1:\n",
    "                    dp[i] = 1\n",
    "                else:\n",
    "                    dp[i] = dp[i-len(word)] + 1\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        ans = 0\n",
    "        words = [word]\n",
    "        while ''.join(words) in sequence:\n",
    "            words.append(word)\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        n, m = len(sequence), len(word)\n",
    "        if n < m:\n",
    "            return 0\n",
    "        \n",
    "        f = [0] * n\n",
    "        for i in range(m - 1, n):\n",
    "            valid = True\n",
    "            for j in range(m):\n",
    "                if sequence[i - m + j + 1] != word[j]:\n",
    "                    valid = False\n",
    "                    break\n",
    "            if valid:\n",
    "                f[i] = (0 if i == m - 1 else f[i - m]) + 1\n",
    "        \n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:       \n",
    "        return next(i for i in range(sequence.count(word), -1, -1) if word * i in sequence) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        maxcount=sequence.count(word)\n",
    "        while True:\n",
    "            if word*maxcount in sequence:\n",
    "                return maxcount\n",
    "            else:\n",
    "                maxcount-=1\n",
    "        return maxcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        for k in range(len(sequence)//len(word),-1,-1):\n",
    "            if word*k in sequence:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        k = 0\n",
    "        str = word\n",
    "        while str in sequence:\n",
    "                k = k + 1\n",
    "                str = str + word\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        k = 0\n",
    "        num = len(sequence) // len(word)\n",
    "        # print(\"num:\", num)\n",
    "        for i in range(1, num + 1):\n",
    "            if (word * i) in sequence:\n",
    "                if i > k:\n",
    "                    k = i\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        # 思路：先求出最高的次数。然后依次 * -1的次数，看看是否包含在原字符串中。\n",
    "        max_count = sequence.count(word)\n",
    "        result = max_count\n",
    "        while True:\n",
    "            if max_count == 0:\n",
    "                break\n",
    "            if word * max_count in sequence:\n",
    "                result = max_count\n",
    "                return result\n",
    "            else:\n",
    "                max_count -= 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        setA = set(sequence)\n",
    "        setB = set(word)\n",
    "        if not setB.issubset(setA):\n",
    "            return 0\n",
    "        # word重复k次仍然是senquence的子串, 所以它自身长度不可能超过senquence\n",
    "        n = len(sequence) // len(word)\n",
    "        k = 0\n",
    "        while n > 0:\n",
    "            index = sequence.find(word * n)\n",
    "            if -1 != index:\n",
    "                k = n\n",
    "                break\n",
    "\n",
    "            else:\n",
    "                n -= 1\n",
    "        return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        left = 0\n",
    "        right = len(sequence) // len(word)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if word * mid in sequence:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        k = 0 \n",
    "        temp = word\n",
    "        \n",
    "        while temp in sequence:\n",
    "            k += 1\n",
    "            temp += word\n",
    "        \n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRepeating(self, sequence: str, word: str) -> int:\n",
    "        i = 0\n",
    "        max_k = 0\n",
    "        L = len(word)\n",
    "        while i < len(sequence):\n",
    "            if sequence[i: i+L] == word:\n",
    "                k = 1\n",
    "                while sequence[i+(L*k): i+(L*(k+1))] == word:\n",
    "                    k += 1\n",
    "                if k > max_k:\n",
    "                    max_k = k\n",
    "            i += 1\n",
    "        return max_k"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
